package cn.fansunion.leecode.number;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.TreeSet;

/**
 * 
 * 第三大的数.
 * 给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
 https://leetcode-cn.com/problems/third-maximum-number/
 * @author wen.lei@brgroup.com
 *
 *         2022-1-12
 */
public class ThirdMaximumNumber {

    /**
     * 第三大的数（自己的原创思考，使用的条件很少，但代码比较多，很难想到，想全面）
     * @param nums
     * @return
     */
    public int thirdMax(int[] nums) {
        //非法情况
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("param invalid");
        }
        //2种特殊情况，不可能存在第3大的(可以判断，也可以不判断,后续的代码已经支持了)
        if (nums.length == 1) {
            return nums[0];
        }
        else if (nums.length == 2) {
            return nums[0] > nums[1] ? nums[0] : nums[1];
        }
        //thirdMax
        Integer max = null;
        Integer secondMax = null;
        Integer thirdMax = null;
        boolean notStop=true;
        for (int num : nums) {
            // 先找到3个不同的值，初始化3个变量
            if (notStop) {
                if (max == null) {
                    max = num;
                    continue;
                } else if (secondMax == null && num != max) {
                    secondMax = num;
                    continue;
                } else if (thirdMax == null && num != max && num != secondMax) {
                    thirdMax = num;
                    //找到3个不同的值，调整
                    int maxReal=max(max,secondMax,thirdMax);
                    int secondMaxReal=secondMax(max,secondMax,thirdMax);
                    int thirdMaxReal=thirdMax(max,secondMax,thirdMax);
                    max=maxReal;
                    secondMax=secondMaxReal;
                    thirdMax=thirdMaxReal;
                    //找3个值，跳出
                    notStop=false;
                    continue;
                }else {
                    //可能一直都是相同的值
                    continue;
                }
            }
            //正常比较,3种情况，比较替换，维护最新的3个最大值
            if (num > max) {
                thirdMax=secondMax;
                secondMax=max;
                max = num;
            } 
            else if (num > secondMax && num < max) {
                thirdMax=secondMax;
                secondMax = num;
            } 
            else if (num > thirdMax && num < secondMax) {
                thirdMax = num;
            }
        }
        //不同的值，不够3的情况
        if(thirdMax==null && secondMax ==null) {
            return max;
        }
        else if(thirdMax==null && secondMax !=null) {
            return Math.max(max, secondMax);
        }
        return thirdMax;
    }

    //3个不同数的第3大
    private int thirdMax(int num1, int num2, int num3) {
        int twoMin=Math.min(num1, num2);
        return Math.min(twoMin,num3);
    }

    //3个不同数的第2大
    private int secondMax(int num1, int num2, int num3) {
       if(num1>num2 && num1 < num3) {
           return num1;
       }else if(num2 > num1 && num2 <num3) {
           return num2;
       }else {
           return num3;
       }
    }

    //3个不同数的第1大
    private int max(int num1, int num2, int num3) {
        int twoMax=Math.max(num1, num2);
        return Math.max(twoMax,num3);
    }

    /**
     * 官方解法，有点无耻，有点“脑筋急转弯”的味道 <br/>
     * (题目中，经常有要求：-2的31方 <= nums[i] <= 2的31方 - 1。我算是明白为啥这么定义了)
     * @param nums
     * @return
     */
    public int thirdMaxIdea(int[] nums) {
        //有向这个方面想，但总觉得不妥吧？
        //数学题和网络上的题，尤其是被定义为“简单题”都很可能有“奇思妙想”的“脑筋急转弯”
        //用这种默认值，避免了thirdMax里面的各种复杂判断
        long max = Long.MIN_VALUE;
        long secondMax = Long.MIN_VALUE;
        long thirdMax =Long.MIN_VALUE;
        for (int num : nums) {
            //正常比较,3种情况，比较替换，维护最新的3个最大值
            if (num > max) {
                thirdMax=secondMax;
                secondMax=max;
                max = num;
            } 
            else if (num > secondMax && num < max) {
                thirdMax=secondMax;
                secondMax = num;
            } 
            else if (num > thirdMax && num < secondMax) {
                thirdMax = num;
            }
        }
        return (int)(thirdMax==Long.MIN_VALUE?max:thirdMax);
    }
    /**
     * 用list和sort排序（这个太容易想到了）
     * 
     * @param nums
     * @return
     */
    public int thirdMaxByListSort(int[] nums) {
        List<Integer> numList=new ArrayList<>();
        //不同的数，放到list
        for(int num:nums) {
            if(!numList.contains(num)) {
                numList.add(num);
            }
        }
        //排序,asc
        Collections.sort(numList);
        if(numList.size() <3) {
            return numList.get(numList.size()-1);
        }
        return numList.get(numList.size()-3);
    }
    
    /**
     * 有序集合（这个有点作弊的感觉）
     * 
     * @param nums
     * @return
     */
    public int thirdMaxByTreeSet(int[] nums) {
        //num放到set
        TreeSet<Integer> ts = new TreeSet<Integer>();
        for(int num:nums) {
            //这个判断不关键,set自带这个逻辑
            if(ts.contains(num)) {
                continue;
            }
            //先放进去，再判断
            ts.add(num);
            if(ts.size()>3) {
                ts.pollFirst();
            }
        }
        if(ts.size()<3) {
            return ts.pollLast();
        }
        return ts.pollFirst();
    }
}
